/*-
 * Copyright 2009-2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *  notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *  notice, this list of conditions and the following disclaimer in the
 *  documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#ifndef __hash_h__
#define __hash_h__
//---------------------------------------------------------------------------
#include "config.h"
//---------------------------------------------------------------------------
#ifdef __cplusplus
extern "C" {
#endif
//---------------------------------------------------------------------------
static __inline__ uint32_t joaat_hash(const uint8_t * key,size_t len)
{
  uint32_t hash = 0;
  size_t i;

  for( i = 0; i < len; i++ ){
    hash += key[i];
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }

  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);

  return hash;
}
//---------------------------------------------------------------------------
#define HASH_PRIME 5381
//---------------------------------------------------------------------------
static __inline__ uint32_t hashf_u32(const uint32_t key,uint32_t h /* = HASH_PRIME*/)
{
  h = (h << 5) + h + ((const uint8_t *) &key)[3];
  h = (h << 5) + h + ((const uint8_t *) &key)[2];
  h = (h << 5) + h + ((const uint8_t *) &key)[1];
  return (h << 5) + h + ((const uint8_t *) &key)[0];
}
//---------------------------------------------------------------------------
static __inline__ uint32_t hashf_uptr(const uintptr_t key,uint32_t h /* = HASH_PRIME*/)
{
#if SIZEOF_INTPTR_T == 8
  h = (h << 5) + h + ((const uint8_t *) &key)[7];
  h = (h << 5) + h + ((const uint8_t *) &key)[6];
  h = (h << 5) + h + ((const uint8_t *) &key)[5];
  h = (h << 5) + h + ((const uint8_t *) &key)[4];
#endif
#if SIZEOF_INTPTR_T == 4 || SIZEOF_INTPTR_T == 8
  h = (h << 5) + h + ((const uint8_t *) &key)[3];
  h = (h << 5) + h + ((const uint8_t *) &key)[2];
  h = (h << 5) + h + ((const uint8_t *) &key)[1];
  return (h << 5) + h + ((const uint8_t *) &key)[0];
#endif
#if SIZEOF_INTPTR_T != 4 && SIZEOF_INTPTR_T != 8
#error must be implemented for arch
#endif
}
//---------------------------------------------------------------------------
static __inline__ uint32_t hashf(const void * key,uintptr_t len,uint32_t h/* = HASH_PRIME*/)
{
  if( len > 0 ){
    for(;;){
      switch( len & 7 ){
        case 0 : h = (h << 5) + h + ((const uint8_t *) key)[7];
        case 7 : h = (h << 5) + h + ((const uint8_t *) key)[6];
        case 6 : h = (h << 5) + h + ((const uint8_t *) key)[5];
        case 5 : h = (h << 5) + h + ((const uint8_t *) key)[4];
        case 4 : h = (h << 5) + h + ((const uint8_t *) key)[3];
        case 3 : h = (h << 5) + h + ((const uint8_t *) key)[2];
        case 2 : h = (h << 5) + h + ((const uint8_t *) key)[1];
        case 1 : h = (h << 5) + h + ((const uint8_t *) key)[0];
      }
      key = (const uint8_t *) key + 8;
      if( len < 8 ) break;
      len -= 8;
    }
  }
  return h;
}
//---------------------------------------------------------------------------
/////////////////////////////////////////////////////////////////////////////
//---------------------------------------------------------------------------
struct hash_node {
  struct hash_node * next;
};
//---------------------------------------------------------------------------
struct hash {
  struct hash_node ** hash_chains;
  struct hash_node * static_hash[16];
  uintptr_t size;
  uintptr_t count;
  uintptr_t node;
  uintptr_t estimated_chain_length;
  uintptr_t threshold_numerator;
  uintptr_t threshold_denominator;

  union {
    void * element_hash;
    uint32_t (* element_hashf)(const void * data);
  };
  union {
    void * element_compare;
    intptr_t (* element_comparef)(const void * data,const void * data_in_hash);
  };
};
//---------------------------------------------------------------------------
struct hash * hash_new(void);
void hash_init(struct hash * h);
void hash_set_node(struct hash * h,const void * data,const struct hash_node * node);
void hash_delete(struct hash * h);
void hash_destroy(struct hash * h);
//---------------------------------------------------------------------------
void * hash_insert(struct hash * h,void * data);
void * hash_remove(struct hash * h,void * data);
void * hash_first(const struct hash * h);
void * hash_lookup(const struct hash * h,const void * data);
//---------------------------------------------------------------------------
static __inline__
struct hash_node * hash_data2node(const struct hash * h,const void * data)
{
  return (struct hash_node *) ((uint8_t *) data + h->node);
}
//---------------------------------------------------------------------------
static __inline__
void * hash_node2data(const struct hash * h,const struct hash_node * node)
{
  return (uint8_t *) node - h->node;
}
//---------------------------------------------------------------------------
uintptr_t hash_max_chain_length(const struct hash * h);
uintptr_t hash_min_chain_length(const struct hash * h);
uintptr_t hash_avg_chain_length(const struct hash * h);
//---------------------------------------------------------------------------
#ifdef __cplusplus
}
#endif
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
